package com.zlm.custom.list;


import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;

/**
 * @author zlm
 * @date 2025/4/28
 */
public class LinkedList<E> implements List<E> {

    private int size;

    private Node<E> head;

    private Node<E> tail;

    @Override
    public void add(E element) {
        Node<E> node = new Node<>(tail,null,element);
        if(tail != null){
            tail.next = node;
        }else{
            head = node;
        }
        tail = node;
        size++;
    }

    @Override
    public void add(int index, E element) {
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException();
        }
        if(index == size){
            //尾插法
            add(element);
            return;
        }
        Node<E> indexNode = findNode(index);
        Node<E> node = new Node<>(indexNode.pre, indexNode, element);
        if(indexNode.pre == null){
            head = node;
        }else{
            indexNode.pre.next = node;
        }
        indexNode.pre = node;
        size++;

    }

    private Node<E> findNode(int index) {
        Node<E> result = null;
        if(index < size/2){
            //从前向后遍历
            result = head;
            for (int i = 0; i < index; i++) {
                result = result.next;
            }

        }else{
            //从后向前遍历
            result = tail;
            for (int i = size-1; i > index; i--) {
                result = result.pre;
            }
        }
        return result;
    }

    @Override
    public E remove(int index) {
        if(index < 0 || index >= size ){
            throw new IndexOutOfBoundsException();
        }
        Node<E> indexNode = findNode(index);
        removeNode(indexNode);
        return indexNode.value;
    }

    private void removeNode(Node<E> node){
        Node<E> pre = node.pre;
        Node<E> next = node.next;
        if(pre == null){
            head = next;
        }else{
            pre.next = next;
        }
        if(next == null){
            tail = pre;
        }else{
            next.pre = pre;
        }
        node.pre = null;
        node.next = null;
        size--;
    }

    @Override
    public boolean remove(E element) {
        Node<E> node = head;
        while (node != null){

            if(Objects.equals(element,node.value)){
                removeNode(node);
                return true;
            }
            node = node.next;
        }

        return false;
    }

    @Override
    public E get(int index) {
        if(index < 0 || index >= size ){
            throw new IndexOutOfBoundsException();
        }
        Node<E> node = findNode(index);

        return node.value;
    }

    @Override
    public E set(int index, E element) {
        if(index < 0 || index >= size ){
            throw new IndexOutOfBoundsException();
        }
        Node<E> oldNode = findNode(index);
        E oldValue = oldNode.value;
        oldNode.value = element;
        return oldValue;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        return new LinkedListIterator();
    }

    class LinkedListIterator implements Iterator<E>{
        Node<E> currentNode = head;

        @Override
        public boolean hasNext() {
            return currentNode!=null;
        }

        @Override
        public E next() {
            if(currentNode == null){
                throw new NoSuchElementException();
            }
            E element = currentNode.value;
            currentNode = currentNode.next;
            return element;
        }
    }

    class Node<E>{
        Node<E> pre;
        Node<E> next;
        E value;
        public Node(E value){
            this.value = value;
        }

        public Node(Node<E> pre, Node<E> next, E value) {
            this.pre = pre;
            this.next = next;
            this.value = value;
        }
    }
}
